Numerically Controlled Milling
Simulating a process of numerically controlled (NC) machining (e.g. milling or turning) is of fundamental importance in computer aided design (CAD) and computer aided manufacturing (CAM). During the simulation, a computer model of a workpiece is edited with a computer representation of a tool, e.g., an NC milling tool, and a set of motions of the tool, which simulate the machining process.
The simulation visualizes the model of the workpiece and the representation of the tool in order to detect potential collisions between parts, such as the workpiece and the tool holder, and to verify a final shape of the workpiece.
The final shape of the workpiece is affected by the selection of the tool and the motions of the tool. Instructions for controlling the motions are typically generated using a computer aided manufacturing system from a graphical representation of a desired final shape of the workpiece. The motions are typically implemented using numerical control programming language, also known as preparatory code or G-Codes, see the following standards RS274D and DIN 66025/ISO 6983.
The G-Codes generated by the computer aided manufacturing system can fail to produce an exact replication of the desired final shape. In addition, the movement of the tool is governed by motors of the NC machining system, which have limited speeds, ranges of motion, and abilities to accelerate and decelerate, so that the actual tool motions sometimes do not exactly follow the NC machining instructions.
Discrepancies between the actual final shape of the workpiece and the desired final shape of the workpiece can be very small, and difficult to see. In some situations, these discrepancies result in undesirable gouges or nicks in the surface of the final shape of the workpiece with sizes on the order of a few micrometers in depth and width, and tens of micrometers in length.
Typically, a set of NC machine instructions is tested by machining a test workpiece made of softer, less expensive material prior to machining the desired part. If visual inspection of the test workpiece locates undesirable discrepancies in the test workpiece, then the NC machining instructions are modified accordingly.
However, this manual testing is time consuming and expensive. Time for machining a single test workpiece may be on the order of hours and several iterations may be required before an acceptable set of NC machine instructions is attained. Thus, it is desirable to test for these discrepancies using computer-based simulation and rendering. Examples of the computer-based simulation are described in U.S. patent application Ser. No. 12/495,588 and No. 12/468,607, incorporated herein by reference.
Tools
FIG. 2A shows a set of typical tools 202, 204, 206, and 208 used in NC milling. When a tool is moved relative to a workpiece 210, the tool carves material out of the workpiece. Here, the tools 202, 204, 206, and 208 remove material, commonly referred as a “swept volume,” corresponding to surfaces 212, 214, 216, and 218 from the workpiece. The shape of the material removed by each tool is determined by the shape of the tool, and the path of the tool relative to the workpiece.
Swept Volumes
During machining, the tool moves relative to the workpiece according to a prescribed motion of the tool, i.e., a tool path, where the tool path can include information about the relative position, orientation, and other shape data of the tool with respect to the workpiece.
As the tool moves along the tool path, the tool carves out the swept volume. During machining, as the tool moves along the tool path, a portion of a volume of the workpiece that is intersected by the swept volume is removed. This material removal can be modeled in the computer as a constructive solid geometry (CSG) difference operation, in which the portion of the workpiece is removed from the workpiece using a CSG subtraction operation of the swept volume from the workpiece.
FIG. 2B shows the swept volume 260 of a shape 250 that is moved along a path 252. The path 252 specifies a position of a particular point of the shape 250 as a function of time. The path can specify an orientation 256, 257, and 258 of the shape as a function of time. The path can also specify a scale of the shape or an arbitrary transformation of the shape as a function of time. In FIG. 2B, the original position, orientation, and geometry of a shape 250 is transformed to a final position, orientation, and geometry of the shape 254 as it moves along the path.
FIG. 3A shows a linear path, in which a tool 302 is moved along a straight line 304.
FIG. 3B shows a circular arc path, in which a tip 310 of the tool 302 is moved along a circular arc 312, and an original axis direction 314 of the tool is transformed to a final axis direction 316 at the end of the path.
FIG. 3C shows a curved path, in which the tip 310 of the tool 302 is moved along a curve 320.
Other possible path forms include positioning the tool at a point, moving the tool along a sequence of lines known as a polyline, moving the tool along a spiral or helical curve, moving the tool along a polynomial curve, such as a quadratic Bezier curve or a cubic Bezier curve, or a sequence of polynomial curves known as a piecewise polynomial curve to name but a few. Any form of path that can be simulated can be considered, including a path defined by a procedure such as a path that is influenced by the shape or material composition of the workpiece.
Distance Fields
A distance field, d(p), of an object is a scalar field whose value at point p in space is the distance from a point p to the surface of the object. Many possible distance fields are known in the prior art, but the most common and useful is a Euclidean distance field where the distance is the minimum distance to the surface of the object, which is defined as d(ps)=0.
Additionally, the distance field is signed to distinguish the outside of the object from the inside, e.g., the d(p)>0 inside and d(p)<0 outside. Also the gradient vector of the distance field at p points in the direction of the minimum distance, and at the surface of the object the normalized gradient vector is equal to the normal vector of the surface. Distance fields are a form of implicit functions and are an effective representation for rendering and editing shapes, as described in U.S. Pat. Nos. 6,396,492, 6,724,393, 6,826,024, and 7,042,458, incorporated herein by reference.
Adaptively sampled distance fields (ADFs) use detail-directed sampling to provide a space and time efficient representation of the distance fields. ADFs store the distance field in a spatial hierarchy of cells. Each cell contains distance data and a reconstruction method for reconstructing the portion of the distance field associated with the cell. Distance data can include the value of the distance field, as well as gradients and partial derivatives of the distance field. The distance field of the cell can be reconstructed as needed to reduce memory and computation requirements.
ADFs can be used to simulate milling using CSG operations. The workpiece to be milled and the milling tool can be represented as ADFs. The simulated milling process can generate an ADF of the simulated workpiece explicitly, for example by modifying an ADF of the workpiece. Alternatively, the simulated workpiece can be represented implicitly as a composite ADF. The composite ADF stores distance fields of the workpiece and the milling tool, operators corresponding to the distance fields, such as a CSG subtraction operator for the milling tool, and a distance field reconstruction method that combines the stored distance fields on demand during rendering or other processing.
The milling tool can be represented by a tool distance field. The tool path can be represented by a parametric function. A swept volume distance field is defined to represent the swept volume generated by moving the milling tool along the path, where the swept volume distance field is defined in a continuous manner according to a swept volume reconstruction method. The swept volume reconstruction method can reconstruct the swept volume distance field at a sample point.
An example of the sample point of particular interest is a point on an isosurface of the distance fields of any objects where a value for distance field d equals zero, i.e., d=0. As referred herein, a zero value isosurface of the distance field of an object is a boundary of the object, e.g., the boundary of the workpiece, or the boundary of the swept volume.
FIG. 1A is a 2D illustration of a composite ADF 100 that consists of a spatial hierarchy of cells, e.g., 101, 102 and 103, representing portions of the volume of the workspace as well as distance fields whose boundaries are indicted. In this example, distance fields 104-107 are planes that defined the boundary of the initial workpiece. Distance fields 108-110 are three distance fields representing sweeps of a ball end mill tool. Each cell in the composite ADF is associated with a subset of the set of distance fields representing the original workpiece and the swept volumes of the milling tool. For example, associated with cell 111 are distance fields 104, 108, and 109 that together determine the composite surface within cell 111. Also associated with the cell is a procedural reconstruction method, such as CSG difference, for combining the subset of the set of distance fields to reconstruct the composite distance field of the workpiece. The composite surface is defined to be the simulated boundary of the workpiece composed of patches of the boundaries of the original workpiece distance fields and the swept tool distance fields.
The subset of the distance fields associated with the cell can be selected by a number of methods. For example, the subset can be limited only to those distance fields where the absolute value of the distance from a center of the cell to the boundary is less than a diameter of a sphere completely enclosing the cell. Alternatively, the subset can be limited only to distance fields representing a swept volume having a boundary wherein at least a portion of the boundary intersects with the cell. Those distance fields can be determined, e.g., by searching, using a boundary/cell intersection test, for a point within the cell where the distance field is equal to zero.
It is desirable, that the subset of the set of distance fields associated with a cell includes only those distance fields that actually form the composite surface within the cell to maximize simulator performance by minimizing the number of distance fields that must be processed during a geometric operation, e.g., rendering. Unfortunately, the aforementioned methods of determining the subset of the distance fields of the cell can result in poor simulator performance, because a number of distance fields of the subset found by those methods can represent swept volumes that enter the cell, but do not form a portion of the workpiece boundary.
FIG. 1 shows an example of a conventional representation of a portion of the workpiece. The composite ADF representing the workpiece includes the set of cells, e.g., a cell 101, and a set of distance fields 102-105 representing the swept volumes of the tool such as the swept volume 110. The portion of the workpiece 107 is represented by the cell 101 and the subset of the swept volume distance fields 103-105. Because a swept volume distance field 102 does not intersect with boundaries of the cell, this distance field is typically not included in the subset. However, as can be seen in this example, the swept volume distance fields 103-104 do not form a portion of the boundary of the workpiece, and thus also should not be included in the subset.
As a specific example, consider a cubic cell aligned to the x, y, and z axes with a side dimension of 400 microns and a spherical tool of radius 2 mm moving in parallel sweeps parallel to the x axis in the x, y plane, where the sweeps are separated by 50 microns, and the tool height is such that the minimum point of the tool is very slightly above the bottom of the cell. Then, 56 tool sweep volumes have the boundaries within the cell, but only 9 of the sweep volumes form the boundary of the workpiece.
Therefore to optimize the performance of the simulation of the milling process, there is a need to optimize the subset of distance fields associated with the cell.